package com.lfg.leetcode.leetcode300;

import java.util.ArrayList;
import java.util.List;


public class No312maxCoins {
    public static void main(String[] args) {
        int ret = maxCoins(new int[]{3, 1, 5, 8});
        System.out.println("[" + ret + "]");
    }


    public static int maxCoins(int[] nums) {
        int[] array = new int[nums.length + 2];
        System.arraycopy(nums, 0, array, 1, nums.length);
        array[0] = 1;
        array[array.length - 1] = 1;
        int[][] dp = new int[array.length][array.length];

        for (int length = 1; length <= nums.length; length++) {
            for (int i = 1; i <= nums.length - length + 1; i++) {
                int j = i + length - 1;
                for (int k = i; k <= j; k++) {
                    int value = array[i - 1] * array[k] * array[j + 1];
                    dp[i][j] = Math.max(dp[i][j], dp[i][k - 1] + dp[k + 1][j] + value);
                }
            }
        }
        return dp[1][nums.length];
    }


    public static int maxCoins2(int[] nums) {
        int ret = 0;
        List<Integer> list = new ArrayList<Integer>(nums.length);
        for (int i : nums) {
            list.add(i);
        }
        for (int i = 0; i < list.size(); i++) {
            ret = Math.max(ret, maxCoins(new ArrayList<>(list), i));
        }
        return ret;
    }

    public static int maxCoins(List<Integer> list, int index) {
        if (index < 0 || index >= list.size()) {
            return 0;
        }
        int left = 1;
        int right = 1;

        if (index > 0 && index < list.size()) {
            left = list.get(index - 1);
        }
        if (index < list.size() - 1) {
            right = list.get(index + 1);
        }
        int val = list.remove(index);
        int total = left * right * val;
        list.remove(index);
        int ret = 0;
        for (int i = 0; i < list.size(); i++) {
            ret = Math.max(ret, maxCoins(list, i));
        }
        list.add(index, val);
        return ret + total;
    }

}
